package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * Description TODO
 *
 * @ClassName algorithm.sort.ShellSort
 * @Version 1.0
 * @Date: 2022/2/15 17:30
 * @Author xuyi
 */
public class ShellSort {
    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        int gap = arr.length/2;
        while(gap>0){
            for(int i=gap;i<arr.length;i++){
                int tmp = arr[i];
                int j = i-gap;
                while(j>=0&&arr[j]>tmp){
                    arr[j+gap] = arr[j];
                    j-=gap;
                }
                arr[j+gap] = tmp;
            }
            gap = Math.floorDiv(gap,2);
        }
    }
}
